//
// Created by hujizhe on 22/1/2024.
//

#ifndef LEETCODE_HASH_H
#define LEETCODE_HASH_H

#include <set>
#include <map>
#include <vector>

using namespace std;

//! 242.有效的字母异位词
bool isAnagram(string s, string t) {
    std::vector<int> s_vec(26, 0);
    std::vector<int> t_vec(26, 0);
    for(const auto &elem : s) {
        s_vec[elem - 'a']++;
    }
    for(const auto &elem : t) {
        t_vec[elem - 'a']++;
    }
    for(int i=0; i<26; i++) {
        if(s_vec[i] != t_vec[i]) return false;
    }
    return true;
}

//! 383.赎金信
bool canConstruct(string ransomNote, string magazine) {
    std::vector<int> vec(26, 0);
    for(const auto& elem : magazine) {
        vec[elem - 'a']++;
    }
    for(const auto& elem : ransomNote) {
        vec[elem - 'a']--;
        if(vec[elem - 'a'] < 0) return false;
    }
    return true;
}

//! 49. 字母异位词分组
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<vector<int>, int> vec_set;
    int index = 0;
    vector<vector<string>> res(strs.size());
    for(const auto& s : strs) {
        vector<int> vec(26, 0);
        for(const auto& elem : s) {
            vec[elem - 'a']++;
        }
        if(vec_set.find(vec) == vec_set.end()) {
            vec_set[vec] = index;
            res[index].push_back(s);
            index++;
        } else {
            res[vec_set[vec]].push_back(s);
        }
    }
    return vector<vector<string>> (res.begin(), res.begin() + index);
}

//! 438. 找到字符串中所有字母异位词
//! 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
vector<int> findAnagrams(string s, string p) {
    if(s.size() < p.size()) return vector<int> ();
    vector<int> p_vec(26, 0);
    vector<int> res;
    for(const auto& elem : p) {
        p_vec[elem - 'a']++;
    }
    for(int j=0; j<=(s.size() - p.size()); j++) {
        vector<int> s_vec = p_vec;
        bool flag = true;
        for(int i=j; i<(j + p.size()); i++) {
            s_vec[s[i] - 'a']--;
            if(s_vec[s[i] - 'a'] < 0) {
                flag = false;
                break;
            }
        }
        if(flag) {
            res.push_back(j);
        }
    }
    return res;
}

//! 349. 两个数组的交集
vector<int> intersection(vector<int> &vec1, vector<int> &vec2) {
    set<int> s{vec1.begin(), vec1.end()};
    set<int> res;
    for(auto & v : vec2) {
        if(s.find(v) != s.end()) {
            res.insert(v);
        }
    }
    return vector<int>(res.begin(), res.end());
}

//! 202. 快乐数

bool isHappy(int n) {
    set<int> s;
    auto func = [](int a) -> std::pair<int, int> {
        std::pair<int,int> res;
        res.first = (a / 10);
        res.second = (a % 10);
        return res;
    };
    while(1) {
        int res = 0;
        std::pair<int, int> cur = func(n);
        while(cur.first >= 10) {
            res += (cur.second) * (cur.second);
            cur = func(cur.first);
        }
        res += (cur.second) * (cur.second);
        res += (cur.first) * (cur.first);
        if(res == 1) {
            return true;
        } else {
            if(s.find(n) != s.end()) {
                return false;
            } else {
                s.insert(n);
                n = res;
            }
        }
    }
}
//! 1.两数之和
vector<int> twoSum(vector<int>&& nums, int target) {
    map<int, int> m;
    for(int i=0; i<nums.size(); i++) {
        if(m.find(nums[i]) != m.end()) {
            return {m[nums[i]], i};
        } else {
            m[target - nums[i]] = i;
        }
    }
    return {};
}

//! 454.四数相加
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    std::map<int, int> ab2cd;
    int count = 0;
    for (int i=0; i<nums1.size(); i++) {
        for (int j=0; j<nums2.size(); j++) {
            ab2cd[0 - nums1[i] - nums2[j]]++;
        }
    }
    for (int i=0; i<nums3.size(); i++) {
        for (int j=0; j<nums4.size(); j++) {
            if(ab2cd.find(nums3[i] + nums4[j]) != ab2cd.end()) {
                count += ab2cd[nums3[i] + nums4[j]];
            }
        }
    }
    return count;
}

vector<string> commonChars(vector<string>& words) {
    vector<bool> common(26, false);
    for(int j=0; j<words[0].size(); j++) {
        common[words[0][j] - 'a'] = true;
    }
    for(int i=1; i<words.size(); i++) {
        for(int j=0; j<words[i].size(); j++) {
            common[words[i][j] - 'a'] = true;
        }
    }
}

void getNext(vector<int> next, string s) {
    next[0] = 0;
    int j = 0;
    for(int i=1; i<s.size(); i++) {
        while(j > 0 && s[i] != s[j]) {
            j = next[i - 1];
        }
        if(s[i] == s[j]) j++;
        next[i] = j;
    }
}
#endif //LEETCODE_HASH_H
